1. Field of the Invention
The present invention relates to a technique to transmit and receive data between a plurality of devices connected in a network environment, and maintain identical data at each one of the plurality of devices.
2. Background Arts
The network environment where the transmission and reception of data between information processing devices (simply referred to as devices) takes place includes not only communication in highly reliable and high speed network environments using a LAN (local area network) and a special channel, but also includes communication using channels that are less reliable and relatively low in speed such as a mobile communication and a public network. Supposing that a device transmits data which is received by another device using the channels mentioned above, in the system where the data can only be stored to a server having sufficiently large memory and high processing performance and data stored in the server is manipulated from other devices, the transmission and reception of data must take place frequently in large amounts, resulting in problems of increased processing time and increased communication cost.
In order to resolve such problems, a method of storing a copy of the server data to each terminal is adopted, and the server data is manipulated from each terminal. However, even by this method, the result of data manipulation that takes place at each terminal must further be transmitted to all other terminals present in the system. As a general method to reduce the communication cost upon transmitting the result of data manipulation to the other terminals, there is a method not to transmit and receive the data itself but to transmit and receive the update log instead. Each terminal stores contents of all other updates of the data which took place at the other terminals as the update logs. When the updated data of each terminal is being synchronized with the data of the other terminals and the server data, then the update logs are transmitted and received instead of the updated data itself. At this time, a conflict between these data may need to be solved. Various well-known techniques are used to treat such conflicts. For instance, when the data is a file in a file system, one can adopt a method mentioned in the following document: P. Reiher, et. al., xe2x80x9cResolving File Conflicts in the Ficus File Systemxe2x80x9d, USENIX Conference Proceedings, pp. 183-195. USENIX, June 1994.
For a first terminal to transmit an update log of the updated data to a second terminal, a method for selecting the update log that is not present in the second terminal is required, among all the update logs that are present in the first terminal. To achieve this selection method, the second terminal that needs to obtain an update log from the first terminal must transfer an information informing a server or the first terminal having all the update logs which one of the update logs are already being stored in the second terminal. This information is called a log record information. Based on the log record information of the second terminal, the update log which is required for transmitting to the second terminal (or to the server) is extracted from the first terminal. The first terminal then transmits the extracted update log to the second terminal.
Accordingly, a content of the update log that is transmitted and received depends on the log record information of the second terminal. It is not generally possible to predict from another terminal which terminal copies data and when such a terminal copies the data of the server. When the terminal does not have the required update log, then the data itself can possibly be transmitted instead of the update log, although this invites a problem of increased amount of data transferring between the terminals. It is therefore desirable that each terminal stores as much of the update logs as possible.
However, a capacity of the non-volatile storage memory at each terminal is limited, and storing all of the update logs there is virtually impossible. Also, storing a large amount of update logs may suppress the capacity of the memory at each terminal which effects other processing that need be performed by the terminal.
If an update log is distributed to all the terminals storing the log record information, then there will be no more terminals that will be requiring this update log. It is then possible to delete this update log. By deleting the update log that is no longer required, the amount of memory which has been used for storing the update logs is decreased.
For example, a version vector that records data updating counts per each terminal is used as the log record information in the following document: Popek, et. al., xe2x80x9cReplication in Ficus Distributed File Systemsxe2x80x9d, Proceedings of the IEEE Workshop on Management of Replicated Data, November, 1990. In another document by D. Ratner, et. al., xe2x80x9cDynamic Version Vector Maintenancexe2x80x9d, UCLA Technical Report CSD-970022, June 1997, an information indicating the data updating counts per each terminal is also included in the version vector. In this document, a verification means called an one-phase bit vector is used to verify that this information included in the version vector is distributed to all the terminals. The one-phase bit vector uses a method to decrement a value of the data updating counts per each terminal by an amount of version vectors distributed to all the terminals. By using this concept, it is possible to delete the update logs, in order from the oldest update log, by a number of times equating to the decremented value of the data updating counts. This means that the update logs which are distributed to all of the terminals can be deleted from all the terminals.
When there are many terminals in a system, verifying whether or not all the terminals store a specific update log is time consuming and is costly because the verification means must also be accompanied by a transmission of the updated content. When engaging a long time in the verification process, the number of update logs that need to be verified will be increased during this verification time. The number of update logs that need be stored in the terminal will also be increased in a case involving many terminals compared to a case involving fewer terminals in the system. For the purpose of avoiding this from happening, the first terminal may inquire all the terminals. However, it is not preferable for the first terminal to directly inquire all the terminals, because this leads to an increase in the communication cost.
Also, suppose that if all the terminals in the system are being used (i.e. all the terminals are turned-on), then even though an enormous amount of time may be required for copying a specific update log to all of the terminals, the update log will eventually be distributed to all of the terminals, and after that the update log can be deleted. However, the update log cannot be deleted if there is a terminal in the system which is not being used for a long period of time, because this terminal which is not being used (i.e. a terminal is turned-off) has not at all received any update logs during the period of non-operation, and therefore this will result in an increased amount of update logs that cannot be deleted from the terminals for a long period of time. Also, when there is a terminal which participated in a system at one time but ceased to participate from a certain point of time, then the update logs could never be deleted using the conventional method.
The present invention attempts to solve the problems described above, aiming to facilitate a deleting of the update logs as early as possible. Also, the present invention aims to reduce an amount of update logs recorded in the memory of a terminal.
According to one aspect of the present invention, an update log management device used in a data sharing system for maintaining and storing a data replicated among a plurality of the devices connected in a network, comprises: a storage for recording a plurality of update logs, wherein each one of the plurality of update logs shows an update of the data; an extracting unit for extracting at least one of update logs from the plurality of update logs stored in the storage to transmit to another device to maintain the identical data among the plurality of devices; a comparing unit for calculating data amount X which is an addition of data amount of the at least one of update logs for transmitting to the another device extracted by the extracting unit, and for calculating data amount Y which is an addition of data amount of the data itself plus data amount of an information indicating that the at least one of update logs is already applied to the data itself, and for comparing the data amount X and the data amount Y; and a transmitting unit for transmitting the data itself and the information indicating that the at least one of update logs is already applied to the data to the another device if the data amount X of at the least one of update logs exceeds the data amount Y (X greater than Y), and for transmitting the at least one of update logs to the another device if the data amount X of the at least one of update logs does not exceed the data amount Y (Xxe2x89xa6Y).
According to another aspect of the present invention, the update log management device further comprises a deleting unit for deleting the at least one of update logs from the storage if X greater than Y is true for all of the devices.
According to another aspect of the present invention, the update log management device includes the storage which records a log record information which is an information indicating which update logs are stored by each one of the plurality of devices. The extracting unit decides the at least one of update logs to transmit to the another device based on the log record information.
According to another aspect of the present invention, the update log management device further comprises an excluding unit for selectively deleting the log record information of an unused device from the storage.
According to another aspect of the present invention, the update log management device includes the excluding unit which sets a time limit beforehand and deletes the log record information from the storage that is not updated during the time limit.
According to another aspect of the present invention, the update log management device includes the update log management device which sets an identifier which specifies a plurality of devices for sharing the data as one domain, and hold the log record information of the plurality of devices identified by the identifier and does not hold the log record information of the other devices.
According to another aspect of the present invention, the update log management device includes the excluding unit which receives a signal from the unused device for requesting deletion of the log record information of the unused device, and deletes the log record information of the unused device.
According to another aspect of the present invention, the update log management device includes the excluding unit which deletes the log record information of a second device stored at a first device when X greater than Y is true for all the data stored in the first device.
According to another aspect of the present invention, an update log management method used in a data sharing system for maintaining and storing an identical data between a plurality of the devices connected in a network, comprises the following steps: recording a plurality of update logs, wherein each one of the plurality of update logs shows an update of the data; extracting at least one of update logs from the plurality of update logs stored in the storage to transmit to another device to maintain the identical data among the plurality of devices; calculating data amount X which is an addition of data amount of the at least one of update logs for transmitting to the another device extracted by the extracting unit, and for calculating data amount Y which is an addition of data amount of the data itself plus data amount of an information indicating that the at least one of update logs is already applied to the data itself, and for comparing the data amount X and the data amount Y; and transmitting the data itself and the information indicating that the at least one of update logs is already applied to the data to the another device if the data amount X of the at least one of update logs exceeds the data amount Y (X greater than Y), and for transmitting the at least one of update logs to the another device if the data amount X of the at least one of update logs does not exceed the data amount Y (Xxe2x89xa6Y).
Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.